package mu.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Classname LeetCode_88
 * @Description 合并两个有序数组
 * 给你两个按非递减顺序排列的整数数组nums1和nums2，另有两个整数m和n，分别表京nums1和nums2中的元素数目。
 * 请你合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。
 * 注意:最终，合并后数组不应由函数返回，而是存储在数组nums1中。
 * 为了应对这种情况，nums1的初始长度为m + n，其中前m个元素表示应合并的元素，后n个元素为0 ，应忽略。nums2的长度为n 。
 *
 * @Date 2023/1/28 17:56
 * @Created by JiangMuyun
 */
public class LeetCode_88 {

    /*public void merge(int[] nums1, int m, int[] nums2, int n){
        for (int i = 0; i < n; ++i) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
    }*/
    /*普通写法*/
    public static void towArrays(int[] nums1,int m, int[] nums2,int n){
        //System.out.println(Arrays.toString(result));
        for (int i = 0; i < n; i++) {
            nums1[m+i] = nums2[i];
        }
        Arrays.sort(nums1);//Arrays工具类自带排序方法，所用的是快速排序
    }
    /*进阶解法*/
    public static void towArrays_plus(int[] nums1,int m, int[] nums2,int n){
        int k = m + n;
        int[] temp = new int[k];
        for (int index = 0,nums1Index = 0,nums2Index = 0; index < k; index++) {
            if (nums1Index >= m){
                //nums1数组元素已经取完，直接取nums2元素值即可
                temp[index] = nums2[nums2Index++];
            } else if (nums2Index >= n) {
                //nums2数组已经取完，直接取nums1元素值即可
                temp[index] = nums1[nums1Index++];
            } else if (nums1[nums1Index] < nums2[nums2Index]) {
                //nums1数组元素值小于nums2数组，取nums1数组的值
                temp[index] = nums1[nums1Index++];
            } else {
                //nums2数组的元素值小于等于nums1左边数组，取nums2数组的值
                temp[index] = nums2[nums2Index++];
            }
        }
        for (int i = 0; i < k; i++) {
            nums1[i] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] nums1 = {1,2,3,0,0,0};
        int[] nums2 = {2,5,6};
        /*普通解法*/
        //towArrays(nums1,3, nums2,3);
        System.out.println(Arrays.toString(nums1));
        /*进阶解法*/
        towArrays_plus(nums1,3, nums2,3);
        System.out.println(Arrays.toString(nums1));
    }
}
